﻿/*
 * 由SharpDevelop创建。
 * 用户： Joy
 * 日期: 2013/10/24
 * 时间: 23:07
 * 
 * 要改变这种模板请点击 工具|选项|代码编写|编辑标准头文件
 */
using System;
using System.Collections.Generic;

namespace FindDepth
{


    /// <summary>
    /// Description of Tree.
    /// </summary>    
    public class Forest
    {
        public class TreeNode
        {
            public Int32 Name { get; set; }
            public Int32 Parent { get; set; }
            public Int32 Weight { get; set; }
            public Int32 Count { get; set; }
            public Boolean IsRoot
            {
                get
                {
                    return Parent == Name;
                }
            }
        }

        public delegate Int32 FindDelegate(Int32 name);



        public FindDelegate Find { get; private set; }



        public Int32 FindDepth(Int32 name)
        {
            if (nodes[name].IsRoot)
                return nodes[name].Weight;
            Int32 root = Find(name);
            return nodes[root].Weight + nodes[name].Weight;
        }

        public void Link(Int32 name, Int32 another)
        {
            Int32 root = Find(name);
            Int32 anotherRoot = Find(another);
            if (nodes[root].Count >= nodes[anotherRoot].Count)
            {
                nodes[anotherRoot].Weight += FindDepth(name) + 1 - nodes[root].Weight;

                nodes[anotherRoot].Parent = root;
                nodes[root].Count += nodes[anotherRoot].Count;
            }
            else
            {
                nodes[anotherRoot].Weight += FindDepth(name) + 1;
                nodes[root].Weight -= nodes[anotherRoot].Weight;

                nodes[root].Parent = anotherRoot;
                nodes[anotherRoot].Count += nodes[root].Count;

            }

        }

        public Forest(Int32 capacity)
        {
            Find = FindWhile;

            nodes = new TreeNode[capacity];
            for (Int32 i = 0; i < nodes.Length; i++)
            {
                nodes[i] = new TreeNode()
                {
                    Name = i,
                    Parent = i,
                    Weight = 0,
                    Count = 1
                };

            }
        }

        public Forest(TreeNode[] nodes)
        {
            Find = FindWhile;
            this.nodes = nodes;
        }

        public Int32 FindRecursive(Int32 name)
        {
            Int32 weight = 0;
            return FindRecursive(name, out weight);
        }

        private Int32 FindRecursive(Int32 name, out Int32 newWeight)
        {
            if (!nodes[nodes[name].Parent].IsRoot)
            {
                nodes[name].Parent = FindRecursive(nodes[name].Parent, out newWeight);
                nodes[name].Weight += newWeight;
            }
            newWeight = nodes[name].Weight;
            return nodes[name].Parent;
        }

        public Int32 FindStack(Int32 name)
        {
            Stack<Int32> s = new Stack<Int32>(nodes.Length);
            while (!nodes[name].IsRoot)
            {
                s.Push(name);
                name = nodes[name].Parent;
            }


            Int32 weight = 0;
            while (s.Count > 0)
            {
                Int32 current = s.Pop();
                nodes[current].Parent = name;
                weight += nodes[current].Weight;
                nodes[current].Weight = weight;
            }
            return name;
        }

        public Int32 FindWhile(Int32 name)
        {
            Int32 root = name;
            Int32 weight = 0;
            while (!nodes[root].IsRoot)
            {
                weight += nodes[root].Weight;
                root = nodes[root].Parent;
            }
            while (!nodes[name].IsRoot)
            {
                Int32 next = nodes[name].Parent;
                nodes[name].Parent = root;
                Int32 tempWeight = nodes[name].Weight;
                nodes[name].Weight = weight;
                weight -= tempWeight;
                name = next;

            }
            return root;
        }

        

        public TreeNode[] nodes;


    }

}
